#pragma once
#include <stdio.h>

/*
* 红黑树过于复杂，本示例采用普通的二叉排序树替代
*/

template <typename T1, typename T2>
class WMap
{
private:
    struct BSortTreeData
    {
        T1 first;
        T2 second;
        BSortTreeData *leftChild = nullptr;
        BSortTreeData *rightChild = nullptr;
        BSortTreeData *parent = nullptr;
    };

    BSortTreeData *m_root = nullptr;
    BSortTreeData *m_head = nullptr; // 配合迭代器使用的，其本身为迭代器的end
    long long int m_size = 0;

    /*
    * 在二叉排序树中查找对应的key值
    * currentNode:查找到的当前节点，调用时初始值为根节点
    * key: 要查找的值
    * parentNode: 当前searchStartNode的父节点,初始值传空指针
    * lastItem:寻找的最后一个节点，若查找到了，则是key对应该节点，否则就是离key最接近的节点
    * 返回值：true-查找到相应的节点 false-未查找到相应的节点
    */
    bool searchItem(BSortTreeData *currentNode, T1 key, BSortTreeData *parentNode, BSortTreeData **lastItem)
    {
        if (!currentNode) {
            *lastItem = parentNode;
            return false;
        }
        if (key < currentNode->first) {
            return searchItem(currentNode->leftChild, key, currentNode, lastItem);
        } else if (currentNode->first < key){
            return searchItem(currentNode->rightChild, key, currentNode, lastItem);
        } else { // 相等的情况
            *lastItem = currentNode;
            return true;
        }
    }

    void clearUseAfterOrderTraverse(BSortTreeData *root)
    {
        if (!root) {
           return;
        }
        clearUseAfterOrderTraverse(root->leftChild);
        clearUseAfterOrderTraverse(root->rightChild);
        delete root;
        root = nullptr;
    }

public:
    ////////////////////////////////////////////////////////////////////////////////
    class iterator
    {
    public:
        typedef T1 valueType;
        typedef T1* pointer;
        typedef T1& reference;
        typedef BSortTreeData NodeType;

        iterator(BSortTreeData *node = nullptr)
        {
            _node = node;
        }

        virtual ~iterator() {}

        // 从这里也能看出来，++i的性能要高些
        iterator& operator ++() // ++i重载
        {
            increase();
            return *this;
        }

        iterator operator ++(int) // i++重载
        {
            iterator temp = *this;
            increase();
            return temp;
        }

        // 从这里也能看出来，--i的性能要高些
       iterator& operator --() // --i重载
       {
           decrease();
           return *this;
       }

       iterator operator --(int) // i--重载
       {
           iterator temp = *this;
           decrease();
           return temp;
       }

        bool operator == (const iterator &other)
        {
            return (this->_node == other._node);
        }

        bool operator != (const iterator &other)
        {
            return (this->_node != other._node);
        }

        NodeType* operator -> ()
        {
            return _node;
        }

        NodeType& operator * ()
        {
            return *_node;
        }

        /*
         * 若当前节点有右子树，则其后继节点为右子树中的最左侧节点
         * 若当前节点无右子树，则需向上回溯，直到找到第一个将其作为左子树的祖先节点
        */
        void increase()
        {
            if(_node->rightChild)
            {
                _node = _node->rightChild;
                while(_node->leftChild)
                {
                    _node = _node->leftChild;
                }
            }
            else
            {
                BSortTreeData *tmpNode = _node->parent;
                while(tmpNode->rightChild == _node)
                {
                    _node = tmpNode;
                    tmpNode = tmpNode->parent;
                }

                if (_node->rightChild != tmpNode)
                {
                    _node = tmpNode;
                }
            }
        }

        /*
         * 若当前节点有左子树，其前驱节点为左子树中的最右侧节点
         * 若当前节点无左子树，则向上回溯，找到第一个将其作为右子树的祖先节点
        */
        void decrease()
        {
            if(_node->leftChild)
            {
                _node = _node->leftChild;
                while(_node->rightChild)
                {
                    _node = _node->rightChild;
                }
            }
            else
            {
                BSortTreeData *tmpNode = _node->parent;
                while(tmpNode->leftChild == _node)
                {
                    _node = tmpNode;
                    tmpNode = tmpNode->parent;
                }

                if (_node->leftChild != tmpNode)
                {
                    _node = tmpNode;
                }
            }
        }

    private:
        BSortTreeData *_node = nullptr;
        BSortTreeData *_header = nullptr;
    };

    ////////////////////////////////////////////////////////////////////////////////
    WMap() {
        m_head = new BSortTreeData();
        m_head->parent = nullptr; // 之后指向root
        m_head->leftChild = m_head; // 之后指向最小节点
        m_head->rightChild = m_head; // 之后指向最大节点
    }
    virtual ~WMap() {
        clear();
        delete m_head;
        m_head = nullptr;
    }

    iterator insert(const T1 &key, const T2 &value)
    {
        if (!m_root) { // 根节点为空
            m_root = new BSortTreeData;
            m_root->leftChild = m_root->rightChild = m_root->parent = nullptr;
            m_root->first = key;
            m_root->second = value;
            ++m_size;
            handleHeader();
            return m_root;
        }

        BSortTreeData *insertItemNode;
        if (searchItem(m_root, key, nullptr, &insertItemNode)) { // 不插入重复的内容
            insertItemNode->second = value;
            return insertItemNode;
        } else {
            BSortTreeData *newNode = new BSortTreeData;
            newNode->first = key;
            newNode->second = value;
            newNode->parent = insertItemNode;
            newNode->leftChild = newNode->rightChild = nullptr;
            if (key < insertItemNode->first) {
               insertItemNode->leftChild = newNode;
            } else if (insertItemNode->first < key) {
                insertItemNode->rightChild = newNode;
            }
            ++m_size;
            handleHeader();
            return newNode;
        }
    }

    bool erase(const T1 &key)
    {
        BSortTreeData *deleteItemNode = nullptr;
        if (!searchItem(m_root, key, nullptr, &deleteItemNode)) {
            return false;
        } else {
             // 为叶子节点时，这种情况实际上可以与下面2种合并，但代码还是清楚些好
            if (!deleteItemNode->leftChild && !deleteItemNode->rightChild) {
                if (!deleteItemNode->parent) { // 若删除的节点是根节点，这种情况属于只有一个根节点
                     m_root = nullptr;
                } else {
                    if (deleteItemNode->parent->leftChild == deleteItemNode) { // 若要删除的节点是其父节点的左子节点
                       deleteItemNode->parent->leftChild = nullptr;
                    } else { // 若要删除的节点是其父节点的右子节点
                       deleteItemNode->parent->rightChild = nullptr;
                    }
                }
                delete deleteItemNode;
            } else if (deleteItemNode->leftChild && !deleteItemNode->rightChild) { // 要删除的节点只有左节点
                if (!deleteItemNode->parent) { // 若删除的节点是根节点
                    m_root = deleteItemNode->leftChild;
                    deleteItemNode->leftChild->parent = nullptr;
                } else {
                    if (deleteItemNode->parent->leftChild == deleteItemNode) { // 若要删除的节点是其父节点的左子节点
                       deleteItemNode->parent->leftChild = deleteItemNode->leftChild;
                    } else { // 若要删除的节点是其父节点的右子节点
                       deleteItemNode->parent->rightChild = deleteItemNode->leftChild;
                    }
                    deleteItemNode->leftChild->parent = deleteItemNode->parent;
                }
                delete deleteItemNode;
            } else if (!deleteItemNode->leftChild && deleteItemNode->rightChild) {  // 要删除的节点只有右节点
                if (!deleteItemNode->parent) { // 若删除的节点是根节点
                    m_root = deleteItemNode->rightChild;
                    deleteItemNode->rightChild->parent = nullptr;
                } else {
                    if (deleteItemNode->parent->leftChild == deleteItemNode) { // 若要删除的节点是其父节点的左子节点
                       deleteItemNode->parent->leftChild = deleteItemNode->rightChild;
                    } else { // 若要删除的节点是其父节点的右子节点
                       deleteItemNode->parent->rightChild = deleteItemNode->rightChild;
                    }
                    deleteItemNode->rightChild->parent = deleteItemNode->parent;
                }
                delete deleteItemNode;
            } else {
                // 要删除的节点左右节点都有的情况下，找最接近改节点数据的前驱（也可以找后继）
                BSortTreeData *leftLastRightNode = deleteItemNode->leftChild;
                BSortTreeData *qianQuNode = deleteItemNode->leftChild;
                // 要删除节点的左子节点开始，一直往右子节点找，便可以找到其前驱
                while (leftLastRightNode) {
                    qianQuNode = leftLastRightNode;
                    leftLastRightNode = qianQuNode->rightChild;
                }
                // 先交换数据，接下来实际上变成了删除前驱节点，删除前驱节点要简单些，所以代码也好处理些
                // 也不用再管删除的节点是否是根节点
                deleteItemNode->first = qianQuNode->first;
                deleteItemNode->second = qianQuNode->second;
                if (qianQuNode == deleteItemNode->leftChild) {
                // 这种情况属于要删除节点的左子节点没有右子节点，那么要删除节点的前驱就是其左子节点
                    if (qianQuNode->leftChild) {
                        qianQuNode->leftChild->parent = qianQuNode->parent;
                    }
                    qianQuNode->parent->leftChild = qianQuNode->leftChild;
                } else {
                // 左子节点有右子节点的情况
                    if (qianQuNode->leftChild) {
                        qianQuNode->leftChild->parent = qianQuNode->parent;
                    }
                    qianQuNode->parent->rightChild = qianQuNode->leftChild;
                }
                delete qianQuNode;
            }
            --m_size;
            handleHeader();
            return true;
        }
    }

    void clear()
    {
        clearUseAfterOrderTraverse(m_root);
    }

    long long int size()
    {
        return m_size;
    }

    T2& operator[](const T1 &key)
    {
        BSortTreeData *lastItemNode;
        if (searchItem(m_root, key, nullptr, &lastItemNode))
        {
            return lastItemNode->second;
        }
        else
        {
            iterator it = insert(key, T2());
            return it->second;
        }
    }

    void handleHeader()
    {
        if (!m_root)
        {
            m_head->parent = nullptr; // 之后指向root
            m_head->leftChild = m_head; // 之后指向最小节点
            m_head->rightChild = m_head; // 之后指向最大节点
        }
        else
        {
            m_head->parent = m_root;
            m_root->parent = m_head;
            BSortTreeData *minNode = m_root;
            while(minNode->leftChild)
            {
                minNode = minNode->leftChild;
            }
            m_head->leftChild = minNode;

            BSortTreeData *maxNode = m_root;
            while(maxNode->rightChild)
            {
                maxNode = maxNode->rightChild;
            }
            m_head->rightChild = maxNode;
        }
    }

    iterator begin()
    {
        return iterator(m_head->leftChild);
    }

    iterator end()
    {
        return iterator(m_head);
    }

};
